Assessment Submission Form

PROJECT TOPIC:¶

Analyzing Community Structures and Bridge Nodes in a Social Network¶

Project Source:¶

This project focuses on a comprehensive analysis of a facebook community social network derived from STANFORD SNAP.

1.0 INTRODUCTION¶

Project Scope:¶

The scope of the project encompasses

  • the investigation of nodes that act as bridges between these communities,
  • and the exploration of the network's overall connectivity and information dissemination paths.
  • the identification of which nodes have a maximal influence within the network

This analysis will employ network construction, various network analysis techniques (including degree distribution, clustering coefficient, density analysis, and centrality analysis), and community detection algorithms.

Project Objectives:¶

Network Construction and Initial Analysis:

To construct a network from the provided dataset and understand its basic properties, such as the number of nodes, number of edges, average degree, and the size of the largest connected component.

Centrality Analysis:

To identify and analyze key nodes within the network based on centrality measures, with a focus on degree centrality and betweenness centrality, to uncover influential individuals or nodes within and across communities.

Bridge Node Identification:

To identify bridge nodes that connect different communities within the network, understanding their role in information flow and network cohesion.

Comparative Analysis with Network Models:

To compare the network's structure and metrics with theoretical models such as Erdős-Rényi (ER), Barabási-Albert (BA), and Watts-Strogatz (WS) to contextualize the network's properties within established network theories.

Insight Generation and Strategic Recommendations:

To generate insights on the social dynamics within the network, based on the analysis of community structures and bridge nodes, and provide strategic recommendations for leveraging influential nodes and bridge nodes for effective information dissemination or other strategic purposes.

2.0 Facebook Network Construct¶

In [1]:
!pip install networkx
Requirement already satisfied: networkx in c:\users\stanley\anaconda3\lib\site-packages (2.8.8)
In [2]:
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
import random
from IPython.display import display, HTML

# Disable scrolling for all outputs
display(HTML("<style>.output_scroll { height: auto !important; }</style>"))

# Read the edge list from CSV
data = pd.read_csv('facebook_combined[1].txt',sep=' ', names=['source', 'target'])

# Create a graph
G = nx.from_pandas_edgelist(data,'source', 'target')

# Drawing the graph with the corrected syntax
plt.figure(figsize=(70, 70))
nx.draw(G, with_labels=False, node_size=600, width=10,node_color='#0000FF', edge_color="grey", pos=nx.spring_layout(G))

plt.show()

The network graph displays a distinct clusters of nodes, indicative of tight-knit communities within a larger network.

2.1.0 Basic Properties of the Graph¶

In [3]:
# Basic properties of the network
degrees = dict(G.degree())
num_nodes = G.number_of_nodes()
num_edges = G.number_of_edges()
average_degree = sum((degrees).values()) / num_nodes
print('Nodes: ',num_nodes)
print('Edges: ',num_edges )
print(f"Average Degree: {average_degree}")
Nodes:  4039
Edges:  88234
Average Degree: 43.69101262688784

The network consists of 4,039 individual entities(nodes) connected by 88234 edges.

On average (Average Degree), each node is linked to approximately 43.69 others, suggesting a well-connected structure with potentially influential nodes facilitating extensive interactions across the network.

Degree distribution

In [4]:
# Degree Distribution

# Get the degree values
degree_values = list(degrees.values())

# Calculate the degree distribution (count of each degree)
degree_distribution = {degree: degree_values.count(degree) for degree in set(degree_values)}

# Visualize the degree distribution
plt.hist(degrees.values(), bins=range(min(degrees.values()), max(degrees.values()) + 2), align='left', rwidth=0.8)
plt.xlabel("Degree")
plt.ylabel("Number of Vertices")
plt.title("Degree Distribution")
plt.show()

The degree distribution plot for the network indicates a scale-free property, with most nodes having few connections and a small number of nodes having many links, resembling a power-law distribution. The steep decline from the peak shows that highly connected hubs are rare but significant in the network's structure. This skewed distribution suggests that while the network is robust against random node failures, it might be susceptible to targeted attacks on these hubs.

Average Clustering Coefficient

In [5]:
# Clustering
# Calculate global clustering coefficient
global_clustering_coefficient = nx.average_clustering(G)

print(f"\nAverage Clustering Coefficient: {global_clustering_coefficient}")
Average Clustering Coefficient: 0.6055467186200876

The average clustering coefficient of approximately 0.606 suggests a high likelihood that two neighbors of a node are also neighbors with each other, indicative of a tightly-knit community structure typical of social networks.

Density

In [6]:
# Density

# Calculate the density of the graph
graph_density = nx.density(G)

# Print the result
print(f"Graph Density: {graph_density}")
Graph Density: 0.010819963503439287

With a graph density of about 0.0108, the network is relatively sparse, indicating that while there are numerous connections, they represent only a small fraction of all possible connections between nodes in the network.

Average Shortest Path

In [7]:
avg_shortest_path_length = nx.average_shortest_path_length(G)
print(f" Average Shortest Path length: {avg_shortest_path_length}")
 Average Shortest Path length: 3.6925068496963913

The average shortest path length of approximately 3.69 in the network signifies that, on average, any node can reach any other node through just a few steps, highlighting the "small-world" nature often observed in social networks.

Theoretical models:-Erdős-Rényi (ER), Barabási-Albert (BA), and Watts-Strogatz (WS)¶

3.0 Synthetic Graphs Construction¶

In [8]:
# Suggesting parameters for Barabási-Albert model
# The parameter 'm' can be approximated by half of the average degree, assuming each new node connects to 'm' existing nodes
m = int(average_degree / 2)
# Erdos-Reiny Graph
erdos_renyi_graph = nx.erdos_renyi_graph (n=len(G), p=graph_density)
# Watts-Strogatz Graph
watts_strogatz_graph = nx.watts_strogatz_graph(n=len(G), k=44, p=0.2)
# Barabasi-Albert Graph
barabasi_albert_graph = nx. barabasi_albert_graph (n=len(G), m=m)
In [9]:
# Function to calculate average degree, degree distribution, and clustering coefficient
def calculate_and_plot(graph, title):
    # Calculate average degree
    avg_degree = np.mean(list(dict(graph.degree()).values()))
    print(f"{title} - Average Degree: {avg_degree}")

    # Calculate degree distribution
    degree_sequence = sorted([d for n, d in graph.degree()], reverse=True)
    plt.figure(figsize=(12, 4))

    plt.subplot(121)
    plt.hist(degree_sequence, bins=range(min(degree_sequence), max(degree_sequence) + 1),color='blue',edgecolor='black', density=True, alpha=0.75)
    plt.title(f"{title} - Degree Distribution")
    plt.xlabel("Degree")
    plt.ylabel("Probability")

    # Calculate clustering coefficient
    clustering_coefficient = nx.average_clustering(graph)
    print(f"{title} - Clustering Coefficient: {clustering_coefficient}")

    # Calculate average shortest path length
    avg_shortest_path_length = nx.average_shortest_path_length(graph)
    print(f"{title} - Average Shortest Path length: {avg_shortest_path_length}")


    plt.subplot(122)
    nx.draw(graph,  with_labels=False,node_size=2, width=1, node_color='blue', edge_color="grey",pos=nx.spring_layout(graph))
    plt.title(f"{title} - Graph Visualization")

    plt.tight_layout()
    plt.show()

# Erdos-Reiny Graph
calculate_and_plot(erdos_renyi_graph, "Erdos-Reiny Graph")

# Watts-Strogatz Graph
calculate_and_plot(watts_strogatz_graph, "Watts-Strogatz Graph")

# Barabasi-Albert Graph
calculate_and_plot(barabasi_albert_graph, "Barabasi-Albert Graph")
Erdos-Reiny Graph - Average Degree: 43.84550631344392
Erdos-Reiny Graph - Clustering Coefficient: 0.010862954515787263
Erdos-Reiny Graph - Average Shortest Path length: 2.6036185575973536
Watts-Strogatz Graph - Average Degree: 44.0
Watts-Strogatz Graph - Clustering Coefficient: 0.3772373889132589
Watts-Strogatz Graph - Average Shortest Path length: 2.8159665647259673
Barabasi-Albert Graph - Average Degree: 41.78162911611785
Barabasi-Albert Graph - Clustering Coefficient: 0.036175858754866445
Barabasi-Albert Graph - Average Shortest Path length: 2.5382861331831386

3.1.0 Properties of Synthetic Graphs¶

Erdős–Rényi Graph:¶

Degree Distribution: Appears normally distributed around the average degree, which is typical for an Erdős–Rényi graph where edges are placed randomly.

Average Degree: 43.579, which is fairly high, suggesting a well-connected graph.

Clustering Coefficient: 0.011, quite low, indicating that neighbors of a node are not likely to be connected to each other.

Average Shortest Path Length: 2.607, which is short, characteristic of a "small-world" network where any node can be reached from any other through only a few steps.

Watts-Strogatz Graph:¶

Degree Distribution: Also seems to have a normal-like distribution which is indicative of the regular lattice from which the Watts-Strogatz model begins before random rewiring.

Average Degree: Exactly 44.0, as this model starts with a fixed number of connections per node.

Clustering Coefficient: 0.377, significantly higher than the Erdős–Rényi graph, reflective of the small-world properties with higher local clustering.

Average Shortest Path Length: 2.816, still indicative of a small-world nature but slightly higher than the Erdős–Rényi graph, likely due to the increased clustering.

Barabási-Albert Graph:¶

Degree Distribution: Shows a power-law distribution, which is a hallmark of scale-free networks. This means that a few nodes have a very high degree (hubs), and many have a low degree.

Average Degree: 41.782, which is comparable to the others but indicates a different structure due to the scale-free nature.

Clustering Coefficient: 0.037, which is higher than Erdős–Rényi but lower than Watts-Strogatz, suggesting moderate local clustering.

Average Shortest Path Length: 2.533, the shortest of the three, implying an efficient network largely due to the influence of hubs.

4.0 Centrality Measures¶

4.1.0 Eigenvector centrality¶

Eigenvector centrality is a measure of the influence of a node within a network. It not only takes into account the number of connections that a node has but also the number of connections its neighbors have, and so on.

In [10]:
# Calculate eigenvector centrality

graph_ev = nx.eigenvector_centrality(G)
graph_top_5 = sorted(graph_ev.items(), key=lambda x: x[1], reverse=True)[:5]
print("Graph's eigenvector centrality",dict(graph_top_5))

#Erdos Renyi Graph's eigenvector centrality
erg_ev = nx.eigenvector_centrality(erdos_renyi_graph)
erg_top_5 = sorted(erg_ev.items(), key=lambda x: x[1], reverse=True)[:5]
print("Erdos Renyi Graph's eigenvector centrality",dict(erg_top_5))

# Watts-Strogatz Graph
wsg_ev = nx.eigenvector_centrality(watts_strogatz_graph)
wsg_ev_top_5 = sorted(wsg_ev.items(), key=lambda x: x[1], reverse=True)[:5]
print("Watts-Strogatz Graph's eigenvector centrality",wsg_ev_top_5)

# barabasi_albert_graph
bag_ev = nx.eigenvector_centrality(barabasi_albert_graph)
bag_ev_top_5 = sorted(bag_ev.items(), key=lambda x: x[1], reverse=True)[:5]
print("barabasi_albert_graph eigenvector centrality",bag_ev_top_5)
Graph's eigenvector centrality {1912: 0.09540696149067629, 2266: 0.08698327767886552, 2206: 0.08605239270584342, 2233: 0.08517340912756598, 2464: 0.08427877475676092}
Erdos Renyi Graph's eigenvector centrality {1611: 0.024145417149380646, 2699: 0.023979973533219047, 2771: 0.023268549748842328, 2420: 0.02320649979902077, 501: 0.02283703573647623}
Watts-Strogatz Graph's eigenvector centrality [(2710, 0.019734354789786916), (3995, 0.019535457549262808), (3955, 0.019273442655861152), (1313, 0.019229978513699047), (1314, 0.019174391684653416)]
barabasi_albert_graph eigenvector centrality [(23, 0.13299429130324678), (22, 0.13027970524328508), (26, 0.12838815272255502), (0, 0.11645422646960671), (25, 0.11445348141894027)]
In [11]:
# Visualization
fig, axs = plt.subplots(2, 2, figsize=(15, 15))

# Draw the Facebook network with eigenvector centrality
pos = nx.spring_layout(G, seed=42)  # for reproducible layout
nx.draw_networkx(G, pos,with_labels= False, ax=axs[0, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node, _ in graph_top_5], node_size=100,
                       node_color='red', ax=axs[0, 0])
axs[0, 0].set_title('Facebook Network')

# Draw the Erdős-Rényi network with eigenvector centrality
pos = nx.spring_layout(erdos_renyi_graph, seed=42)
nx.draw_networkx(erdos_renyi_graph, pos,with_labels= False, ax=axs[0, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(erdos_renyi_graph, pos, nodelist=[node for node, _ in erg_top_5],node_size=100,
                       node_color='red', ax=axs[0, 1])
axs[0, 1].set_title('Erdős-Rényi Network')

# Draw the Watts-Strogatz network with eigenvector centrality
pos = nx.spring_layout(watts_strogatz_graph, seed=42)
nx.draw_networkx(watts_strogatz_graph, pos,with_labels= False, ax=axs[1, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(watts_strogatz_graph, pos, nodelist=[node for node, _ in wsg_ev_top_5],node_size=100,
                       node_color='red', ax=axs[1, 0])
axs[1, 0].set_title('Watts-Strogatz Network')

# Draw the Barabási-Albert network with eigenvector centrality
pos = nx.spring_layout(barabasi_albert_graph, seed=42)
nx.draw_networkx(barabasi_albert_graph, pos, with_labels= False, ax=axs[1, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(barabasi_albert_graph, pos, nodelist=[node for node, _ in bag_ev_top_5], node_size=100,
                       node_color='red', ax=axs[1, 1])
axs[1, 1].set_title('Barabasi Albert Graph')
Out[11]:
Text(0.5, 1.0, 'Barabasi Albert Graph')

4.1.1 Top Five Nodes of Graphs-Eigenvector Centrality¶

Facebook Graph:¶

  1. Node 1912 has the highest eigenvector centrality at approximately 0.095, suggesting it's the most influential node in this network.

  2. The nodes listed are the top five in terms of eigenvector centrality, implying they are key players in the network's structure and connectivity.

Erdős–Rényi Graph:¶

  1. Node 1722 is the most influential with an eigenvector centrality score of about 0.024.

  2. The centrality values are much lower compared to the unnamed graph, which might suggest a more uniform distribution of node influence or a less hierarchical structure.

Watts-Strogatz Graph:¶

  1. The nodes listed (e.g., 3926, 344) have lower eigenvector centrality scores compared to the unnamed graph, around 0.02.
  2. This suggests that even the most influential nodes in this network have less individual influence than the most influential nodes in the first network.

Barabási–Albert Graph:¶

  1. The nodes have higher eigenvector centrality scores compared to the other graphs, with node 22 being the most influential at approximately 0.148.
  2. The higher values reflect the scale-free nature of the network, with a few nodes (hubs) holding a significant amount of influence over the network.

4.2.0 Pagerank¶

Unlike eigenvector centrality, which considers a node's influence based on its connections and those of its neighbors, PageRank also factors in the structure of the entire network and the importance of the nodes linking to a given node.

In [12]:
# Calculate the Pagerank
G_pagerank = nx.pagerank(G, alpha=0.85)
G_pk_top_5= sorted(G_pagerank.items(), key=lambda x: x[1], reverse=True)[:5]

# Erdos Renyi Graph
Er_pagerank = nx.pagerank(erdos_renyi_graph, alpha=0.85)
er_pk_top_5= sorted(Er_pagerank.items(), key=lambda x: x[1], reverse=True)[:5]

# Watts-Strogatz Graph
ws_pagerank = nx.pagerank(watts_strogatz_graph, alpha=0.85)
ws_pk_top_5= sorted(ws_pagerank.items(), key=lambda x: x[1], reverse=True)[:5]

# barabasi_albert_graph
ba_pagerank = nx.pagerank(barabasi_albert_graph, alpha=0.85)
ba_pk_top_5= sorted(ba_pagerank.items(), key=lambda x: x[1], reverse=True)[:5]

print("Graph Pagerank",G_pk_top_5)
print("Erdos Renyi Graph Pagerank",er_pk_top_5)
print("Watts-Strogatz Graph Pagerank",ws_pk_top_5)
print("Barabasi_albert_graph Pagerank",ba_pk_top_5)
Graph Pagerank [(3437, 0.0076145868447496), (107, 0.006936420955866117), (1684, 0.006367162138306824), (0, 0.006289602618466542), (1912, 0.003876971600884498)]
Erdos Renyi Graph Pagerank [(2699, 0.0003585213474879747), (1611, 0.0003527570234381428), (501, 0.000344603845673788), (1993, 0.00034444398903447953), (2725, 0.00034441896617056476)]
Watts-Strogatz Graph Pagerank [(2315, 0.00029118697637796456), (3481, 0.00029107407434911535), (150, 0.0002907817291139934), (3870, 0.0002905637670833855), (1314, 0.0002902312087441819)]
Barabasi_albert_graph Pagerank [(23, 0.0024461296569696996), (22, 0.002398036380243977), (26, 0.002290322756389125), (34, 0.002146804066698506), (0, 0.002126607224137006)]
In [13]:
# Visualization
fig, axs = plt.subplots(2, 2, figsize=(15, 15))

# Draw the Facebook network with Pagerank centrality
pos = nx.spring_layout(G, seed=42)  # for reproducible layout
nx.draw_networkx(G, pos,with_labels= False, ax=axs[0, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node, _ in G_pk_top_5], node_size=100,
                       node_color='red', ax=axs[0, 0])
axs[0, 0].set_title('Facebook Network')

# Draw the Erdős-Rényi network with Pagerank centrality
pos = nx.spring_layout(erdos_renyi_graph, seed=42)
nx.draw_networkx(erdos_renyi_graph, pos,with_labels= False, ax=axs[0, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(erdos_renyi_graph, pos, nodelist=[node for node, _ in er_pk_top_5], node_size=100,
                       node_color='red', ax=axs[0, 1])
axs[0, 1].set_title('Erdős-Rényi Network')

# Draw the Watts-Strogatz network with Pagerank centrality
pos = nx.spring_layout(watts_strogatz_graph, seed=42)
nx.draw_networkx(watts_strogatz_graph, pos,with_labels= False, ax=axs[1, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(watts_strogatz_graph, pos, nodelist=[node for node, _ in ws_pk_top_5], node_size=100,
                       node_color='red', ax=axs[1, 0])
axs[1, 0].set_title('Watts-Strogatz Network')

# Draw the Barabási-Albert network with Pagerank centrality
pos = nx.spring_layout(barabasi_albert_graph, seed=42)
nx.draw_networkx(barabasi_albert_graph, pos,with_labels= False, ax=axs[1, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(barabasi_albert_graph, pos, nodelist=[node for node, _ in ba_pk_top_5], node_size=100,
                       node_color='red', ax=axs[1, 1])
axs[1, 1].set_title('Barabasi Albert Graph')
Out[13]:
Text(0.5, 1.0, 'Barabasi Albert Graph')

Top 5 Pagerank in Graphs:

Facebook Graph:

The PageRank scores are higher with node 3437 having the highest PageRank, indicating that this node, along with others like node 107, is likely central in the information flow within the network. These nodes can be considered as important spreaders of information or influence.

Erdős-Rényi Graph:

The top PageRank nodes have values around 0.0025, which are significantly lower than those in the original graph, reflecting the uniform probability of connections between nodes in Erdős-Rényi networks and a more distributed importance among nodes.

Watts-Strogatz Graph:

The PageRank values are very low, around 0.0003, possibly due to the uniform connection pattern before rewiring and the small-world nature which distributes the PageRank more evenly among the nodes.

Barabási-Albert Graph:

The provided PageRank values for the Barabási-Albert graph are identical to those from the Erdős-Rényi graph, which seems like a reporting error. In theory, the Barabási-Albert graph should exhibit a few nodes with significantly higher PageRank scores, reflecting the scale-free nature of the network where some nodes (hubs) dominate the connections.

4.3.0 Degree Centrality¶

Degree centrality is a measure of the number of direct connections (or edges) a node has. Nodes with high degree centrality are considered highly active or influential within the network because they interact with many other nodes.

In [14]:
# Degree Centrality
G_degree_centrality = nx.degree_centrality(G)
G_dc_top_5= sorted(G_degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]

#Erdos Renyi Graph
er_degree_centrality = nx.degree_centrality(erdos_renyi_graph)
er_dc_top_5= sorted(er_degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


# Watts-Strogatz Graph
ws_degree_centrality = nx.degree_centrality(watts_strogatz_graph)
ws_dc_top_5= sorted(ws_degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


ba_degree_centrality = nx.degree_centrality(barabasi_albert_graph)
ba_dc_top_5= sorted(ba_degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


print("Graph Degree Centrality:",G_dc_top_5 )
print("Erdos Renyi Degree Centrality:", er_dc_top_5)
print("Watts Strogatz Degree Centrality:", ws_dc_top_5)
print("Barabasi Albert Degree Centrality:", ba_dc_top_5)
Graph Degree Centrality: [(107, 0.258791480931154), (1684, 0.1961367013372957), (1912, 0.18697374938088163), (3437, 0.13546310054482416), (0, 0.08593363051015354)]
Erdos Renyi Degree Centrality: [(2699, 0.01659237246161466), (1611, 0.016344725111441305), (501, 0.0158494304110946), (1993, 0.0158494304110946), (2420, 0.0158494304110946)]
Watts Strogatz Degree Centrality: [(150, 0.013125309559187715), (1313, 0.013125309559187715), (1314, 0.013125309559187715), (2315, 0.013125309559187715), (2710, 0.013125309559187715)]
Barabasi Albert Degree Centrality: [(23, 0.1183754333828628), (22, 0.11639425458147597), (26, 0.11119366022783556), (34, 0.1030212976721149), (0, 0.10277365032194155)]
In [15]:
# Visualization
fig, axs = plt.subplots(2, 2, figsize=(15, 15))

# Draw the Facebook network with Degree centrality
pos = nx.spring_layout(G, seed=42)  # for reproducible layout
nx.draw_networkx(G, pos, with_labels= False,ax=axs[0, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node, _ in G_dc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 0])
axs[0, 0].set_title('Facebook Network')

# Draw the Erdős-Rényi network with Degree centrality
pos = nx.spring_layout(erdos_renyi_graph, seed=42)
nx.draw_networkx(erdos_renyi_graph, pos, with_labels= False, ax=axs[0, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(erdos_renyi_graph, pos, nodelist=[node for node, _ in er_dc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 1])
axs[0, 1].set_title('Erdős-Rényi Network')

# Draw the Watts-Strogatz network with Degree centrality
pos = nx.spring_layout(watts_strogatz_graph, seed=42)
nx.draw_networkx(watts_strogatz_graph, pos,with_labels= False, ax=axs[1, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(watts_strogatz_graph, pos, nodelist=[node for node, _ in ws_dc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 0])
axs[1, 0].set_title('Watts-Strogatz Network')

# Draw the Barabási-Albert network with Degree centrality
pos = nx.spring_layout(barabasi_albert_graph, seed=42)
nx.draw_networkx(barabasi_albert_graph, pos,with_labels= False, ax=axs[1, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(barabasi_albert_graph, pos, nodelist=[node for node, _ in ba_dc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 1])
axs[1, 1].set_title('Barabasi Albert Graph')
Out[15]:
Text(0.5, 1.0, 'Barabasi Albert Graph')

The degree centrality top five nodes are:

Facebook Network:

Node 107 is the most central with a degree centrality of approximately 0.259, indicating it has the most connections.

Erdős-Rényi Network:

Node 1722 has the highest degree centrality, though the values are much lower than those in the Facebook network, suggesting a more uniform distribution of connections.

Watts-Strogatz Network:

Node 3300 has the highest degree centrality, but similar to the Erdős-Rényi network, the values are quite low, which is typical for Watts-Strogatz networks that start with a regular lattice structure.

Barabási-Albert Graph:

Node 23 is the most central, which is in line with the Barabási-Albert network's tendency to have a few nodes (hubs) with a large number of connections.

4.4.0 Closeness Centrality¶

Closeness centrality is a measure of how close a node is to all other nodes in the network, calculated by the inverse of the average shortest path length from the node to all other nodes.

In [16]:
# Closeness Centrality
G_closeness_centrality = nx.closeness_centrality(G)
G_cc_top_5= sorted(G_closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


er_closeness_centrality = nx.closeness_centrality(erdos_renyi_graph)
er_cc_top_5= sorted(er_closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


ws_closeness_centrality = nx.closeness_centrality(watts_strogatz_graph)
ws_cc_top_5= sorted(ws_closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


ba_closeness_centrality = nx.closeness_centrality(barabasi_albert_graph)
ba_cc_top_5= sorted(ba_closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]

print("Graph Closeness Centrality:", G_cc_top_5)
print("Erdos Renyi Graph Closeness Centrality:", er_cc_top_5)
print("Watts Strogatz Graph Closeness Centrality:", ws_cc_top_5)
print("Barabasi Albert Graph Closeness Centrality:", ba_cc_top_5)
Graph Closeness Centrality: [(107, 0.45969945355191255), (58, 0.3974018305284913), (428, 0.3948371956585509), (563, 0.3939127889961955), (1684, 0.39360561458231796)]
Erdos Renyi Graph Closeness Centrality: [(1611, 0.4077964047667138), (2699, 0.40750832576445656), (2420, 0.405666063893912), (2771, 0.40521826392373306), (2963, 0.4044066099148723)]
Watts Strogatz Graph Closeness Centrality: [(1031, 0.36829624224735497), (3850, 0.3681283617467408), (3995, 0.36792710706150344), (1519, 0.36745836745836746), (1680, 0.3672244452528192)]
Barabasi Albert Graph Closeness Centrality: [(23, 0.5311061423122452), (22, 0.5304085117562065), (26, 0.5286724273369993), (0, 0.5261923377638781), (27, 0.525849720015627)]
In [17]:
# Visualization
fig, axs = plt.subplots(2, 2, figsize=(15, 15))

# Draw the Facebook network with Closeness centrality
pos = nx.spring_layout(G, seed=42)  # for reproducible layout
nx.draw_networkx(G, pos, ax=axs[0, 0],with_labels= False, node_size=20, alpha=0.7)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node, _ in G_cc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 0])
axs[0, 0].set_title('Facebook Network')

# Draw the Erdős-Rényi network with Closeness centrality
pos = nx.spring_layout(erdos_renyi_graph, seed=42)
nx.draw_networkx(erdos_renyi_graph, pos,with_labels= False, ax=axs[0, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(erdos_renyi_graph, pos, nodelist=[node for node, _ in er_cc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 1])
axs[0, 1].set_title('Erdős-Rényi Network')

# Draw the Watts-Strogatz network with Closeness centrality
pos = nx.spring_layout(watts_strogatz_graph, seed=42)
nx.draw_networkx(watts_strogatz_graph, pos,with_labels= False, ax=axs[1, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(watts_strogatz_graph, pos, nodelist=[node for node, _ in ws_cc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 0])
axs[1, 0].set_title('Watts-Strogatz Network')

# Draw the Barabási-Albert network with Closeness centrality
pos = nx.spring_layout(barabasi_albert_graph, seed=42)
nx.draw_networkx(barabasi_albert_graph, pos,with_labels= False, ax=axs[1, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(barabasi_albert_graph, pos, nodelist=[node for node, _ in ba_cc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 1])
axs[1, 1].set_title('Barabasi Albert Graph')
Out[17]:
Text(0.5, 1.0, 'Barabasi Albert Graph')

The top nodes by closeness centrality for each network:

Facebook Network:

Node 107 has the highest closeness centrality, indicating it can spread information very efficiently throughout the network due to its short paths to other nodes.

Erdős-Rényi Network:

Node 1722 has the highest closeness centrality, suggesting it has relatively short paths to other nodes in the network, despite the network's randomness.

Watts-Strogatz Network:

Node 1558 is the most central by this measure, which is consistent with the small-world properties of the network where most nodes can be reached from every other by a small number of steps.

Barabási-Albert Graph:

Node 23 has the highest closeness centrality, further underscoring its central role within this scale-free network.

4.5.0. Betweenness Centrality¶

Betweenness centrality measures the extent to which a node lies on paths between other nodes. Nodes with high betweenness centrality have a significant amount of control over the information flow within the network because they can influence the passing of information through the network

In [18]:
# Betweenness Centrality
G_betweenness_centrality = nx.betweenness_centrality(G)
G_bc_top_5= sorted(G_betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]



er_betweenness_centrality = nx.betweenness_centrality(erdos_renyi_graph)
er_bc_top_5= sorted(er_betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]



ws_betweenness_centrality = nx.betweenness_centrality(watts_strogatz_graph)
ws_bc_top_5= sorted(ws_betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]



ba_betweenness_centrality = nx.betweenness_centrality(barabasi_albert_graph)
ba_bc_top_5= sorted(ba_betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


print("Graph Betweenness Centrality:", G_bc_top_5)
print("Erdos Renyi Graph Betweenness Centrality:", er_bc_top_5)
print("Watts Strogatz Graph Betweenness Centrality:", ws_bc_top_5)
print("Barabasi Albert Graph Betweenness Centrality:", ba_bc_top_5)
Graph Betweenness Centrality: [(107, 0.4805180785560152), (1684, 0.3377974497301992), (3437, 0.23611535735892905), (1912, 0.2292953395868782), (1085, 0.14901509211665306)]
Erdos Renyi Graph Betweenness Centrality: [(2699, 0.0009089813285431107), (1611, 0.0008763509066200602), (1993, 0.0008374087874907576), (501, 0.0008234633934026272), (2771, 0.0008218907118069083)]
Watts Strogatz Graph Betweenness Centrality: [(3850, 0.0011380059715734247), (3995, 0.001075379612747807), (150, 0.0010322542545560332), (746, 0.001006948147238216), (1314, 0.0010001359045145)]
Barabasi Albert Graph Betweenness Centrality: [(23, 0.024452417888801942), (22, 0.022569601392070607), (26, 0.021093983157365468), (34, 0.01870170291154627), (0, 0.018649888752068473)]
In [19]:
# Visualization
fig, axs = plt.subplots(2, 2, figsize=(15, 15))

# Draw the Facebook network with Betweenness centrality
pos = nx.spring_layout(G, seed=42)  # for reproducible layout
nx.draw_networkx(G, pos,with_labels= False, ax=axs[0, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node, _ in G_bc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 0])
axs[0, 0].set_title('Facebook Network')

# Draw the Erdős-Rényi network with Betweenness centrality
pos = nx.spring_layout(erdos_renyi_graph, seed=42)
nx.draw_networkx(erdos_renyi_graph, pos,with_labels= False, ax=axs[0, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(erdos_renyi_graph, pos, nodelist=[node for node, _ in er_bc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 1])
axs[0, 1].set_title('Erdős-Rényi Network')

# Draw the Watts-Strogatz network with Betweenness centrality
pos = nx.spring_layout(watts_strogatz_graph, seed=42)
nx.draw_networkx(watts_strogatz_graph, pos,with_labels= False, ax=axs[1, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(watts_strogatz_graph, pos, nodelist=[node for node, _ in ws_bc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 0])
axs[1, 0].set_title('Watts-Strogatz Network')

# Draw the Barabási-Albert network with Betweenness centrality
pos = nx.spring_layout(barabasi_albert_graph, seed=42)
nx.draw_networkx(barabasi_albert_graph, pos,with_labels= False, ax=axs[1, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(barabasi_albert_graph, pos, nodelist=[node for node, _ in ba_bc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 1])
axs[1, 1].set_title('Barabasi Albert Graph')
Out[19]:
Text(0.5, 1.0, 'Barabasi Albert Graph')

The top five betweenness centrality values provided:

Facebook Network:

Node 107 has the highest betweenness centrality, indicating it acts as a significant bridge or connector within the network.

Erdős-Rényi Network:

Node 1722 has the highest betweenness centrality, but the overall low values suggest that no single node is overwhelmingly critical for the connectivity of the network, which aligns with the random nature of Erdős-Rényi networks.

Watts-Strogatz Network:

Node 344 has the highest betweenness centrality, although the values are not very high, which is typical for networks with a high degree of local clustering and short path lengths like the Watts-Strogatz network.

Barabási-Albert Graph:

Node 23 has the highest betweenness centrality, reinforcing its role as a hub in this scale-free network, likely being on many of the shortest paths across the network.

4.6.0 Katz Centrality¶

Katz centrality measures the influence of a node within a network by considering the total number of direct and indirect paths to other nodes, with more weight given to shorter paths. It's similar to eigenvector centrality but takes into account the number of walks between nodes, penalized by a factor related to the walk length.

In [20]:
# Katz Centrality
G_katz_centrality = nx.katz_centrality(G,alpha=0.005, max_iter=5000, tol=1e-04)
G_kc_top_5= sorted(G_katz_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


er_katz_centrality = nx.katz_centrality(erdos_renyi_graph,alpha=0.005, max_iter=5000, tol=1e-04)
er_kc_top_5= sorted(er_katz_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


ws_katz_centrality = nx.katz_centrality(watts_strogatz_graph,alpha=0.005, max_iter=5000, tol=1e-04)
ws_kc_top_5= sorted(ws_katz_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


ba_katz_centrality = nx.katz_centrality(barabasi_albert_graph,alpha=0.005, max_iter=5000, tol=1e-04)
ba_kc_top_5= sorted(ba_katz_centrality.items(), key=lambda x: x[1], reverse=True)[:5]


print("Graph Katz Centrality:", G_kc_top_5)
print("Erdos Renyi Graph Katz Centrality:", er_kc_top_5)
print("Watts Strogatz Graph Katz Centrality:", ws_kc_top_5)
print("Barabasi Albert Graph Katz Centrality:", ba_kc_top_5)
Graph Katz Centrality: [(1912, 0.09154354521626484), (107, 0.07901729505345785), (2347, 0.060825573158024684), (2543, 0.05841876022404456), (2266, 0.05692369340294383)]
Erdos Renyi Graph Katz Centrality: [(2699, 0.01755763537003326), (1611, 0.017506289025496148), (2771, 0.017344240226912867), (2420, 0.017332431713531635), (501, 0.01731511667200845)]
Watts Strogatz Graph Katz Centrality: [(2710, 0.01645521444047997), (3995, 0.01644982651767973), (1313, 0.01644603703059488), (3870, 0.01644437271002515), (1314, 0.016443105310566097)]
Barabasi Albert Graph Katz Centrality: [(23, 0.05605575235373262), (22, 0.0551701849832444), (26, 0.053806414451501035), (0, 0.05030280413280131), (27, 0.04939106346966843)]
In [21]:
# Visualization
fig, axs = plt.subplots(2, 2, figsize=(15, 15))

# Draw the Facebook network with Katz centrality
pos = nx.spring_layout(G, seed=42)  # for reproducible layout
nx.draw_networkx(G, pos,with_labels= False, ax=axs[0, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node, _ in G_kc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 0])
axs[0, 0].set_title('Facebook Network')

# Draw the Erdős-Rényi network with Katz centrality
pos = nx.spring_layout(erdos_renyi_graph, seed=42)
nx.draw_networkx(erdos_renyi_graph, pos,with_labels= False, ax=axs[0, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(erdos_renyi_graph, pos, nodelist=[node for node, _ in er_kc_top_5], node_size=100,
                       node_color='red', ax=axs[0, 1])
axs[0, 1].set_title('Erdős-Rényi Network')

# Draw the Watts-Strogatz network with Katz centrality
pos = nx.spring_layout(watts_strogatz_graph, seed=42)
nx.draw_networkx(watts_strogatz_graph, pos,with_labels= False, ax=axs[1, 0], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(watts_strogatz_graph, pos, nodelist=[node for node, _ in ws_kc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 0])
axs[1, 0].set_title('Watts-Strogatz Network')

# Draw the Barabási-Albert network with Katz centrality
pos = nx.spring_layout(barabasi_albert_graph, seed=42)
nx.draw_networkx(barabasi_albert_graph, pos,with_labels= False, ax=axs[1, 1], node_size=20, alpha=0.7)
nx.draw_networkx_nodes(barabasi_albert_graph, pos, nodelist=[node for node, _ in ba_kc_top_5], node_size=100,
                       node_color='red', ax=axs[1, 1])
axs[1, 1].set_title('Barabasi Albert Graph')
Out[21]:
Text(0.5, 1.0, 'Barabasi Albert Graph')

The Katz centrality scores for the top 5 nodes in each network:

Facebook Network:

Node 1912 has the highest Katz centrality, suggesting that it is very well-connected, both directly and through its neighbors.

Erdős-Rényi Network:

Node 1722 tops the list with a much lower Katz centrality than seen in the Facebook network, indicating that while it has many connections within the network, those connections may not be as influential.

Watts-Strogatz Network:

Node 3300 has the highest Katz centrality, reflecting its influence within the network through both its direct ties and the numerous short paths connecting it to other nodes.

Barabási-Albert Graph:

Node 23 has the highest Katz centrality, consistent with its role as a hub in the network's scale-free topology.

5.0 Models of Influence¶

5.1.0.Linear Threshold Model (LTM) and Independent Cascade Model (ICM) on Facebook Network

In the Linear Threshold Model (LTM), nodes become active if a certain threshold of their neighbors are active. The model is deterministic in nature, meaning if the active neighbors exceed the threshold, the node will definitely become active. In the ICM, active nodes have a single chance to activate each of their inactive neighbors independently. The process is stochastic, with a certain probability assigned to the activation of each edge.

In [22]:
# Define the Linear Threshold Model (LTM)
def linear_threshold_model(graph, thresholds, seed_size):
    # Initial set of active nodes
    initial_active = random.sample(list(graph.nodes), seed_size)
    active = set(initial_active)
    next_active = set(initial_active)

    while next_active:
        current_active = next_active
        next_active = set()
        for node in set(graph.nodes()) - active:
            # Count the number of active neighbors
            active_neighbors = sum([1 for neighbor in graph.neighbors(node) if neighbor in current_active])
            # If the number of active neighbors exceeds the threshold, activate the node
            if active_neighbors / graph.degree(node) >= thresholds[node]:
                next_active.add(node)
        active.update(next_active)

    return active

# Define the Independent Cascade Model (ICM)
def independent_cascade_model(graph, probability, seed_size):
    # Initial set of active nodes
    initial_active = random.sample(list(graph.nodes), seed_size)
    active = set(initial_active)
    next_active = set(initial_active)

    while next_active:
        current_active = next_active
        next_active = set()
        for node in current_active:
            for neighbor in graph.neighbors(node):
                if neighbor not in active and random.random() < probability:
                    next_active.add(neighbor)
        active.update(next_active)

    return active

# Define thresholds for LTM as a fraction of the node's degree
ltm_thresholds = {node: 0.5 for node in G.nodes()}  # Set a threshold of 50% of the neighbor's influence

# Set the probability of influence for ICM
icm_probability = 0.1  # 10% chance of influencing a neighbor

# Set the size of the initial seed
seed_size = 10

# Run the models
ltm_active_nodes = linear_threshold_model(G, ltm_thresholds, seed_size)
icm_active_nodes = independent_cascade_model(G, icm_probability, seed_size)

# Print the results
print(f"Active nodes in LTM: {len(ltm_active_nodes)}")
print(f"Active nodes in ICM: {len(icm_active_nodes)}")

# Draw the graph
plt.figure(figsize=(12, 8))
pos = nx.spring_layout(G)
nx.draw_networkx_edges(G, pos, alpha=0.1)
nx.draw_networkx_nodes(G, pos, nodelist=ltm_active_nodes,node_size=6, node_color='r', label='LTM Active Nodes')
nx.draw_networkx_nodes(G, pos, nodelist=icm_active_nodes,node_size=6, node_color='b', label='ICM Active Nodes')
plt.legend()
plt.title('Linear Threshold Model and Independent Cascade Model on Facebook Network')
plt.show()
Active nodes in LTM: 10
Active nodes in ICM: 3033

The visualization shows a striking difference in the number of active nodes under the two models:

LTM Active Nodes: There are only 10 active nodes, marked in red, indicating that under the threshold settings of this model, only a few nodes were activated based on their neighbors' influence.

ICM Active Nodes: A significantly higher number, 3,033 nodes, marked in blue, suggests that the independent chance of activation spread across the network much more effectively.

5.2.0. Linear Threshold Model and Independent Cascade Model on Erdos Renyi Network

In [27]:
G=erdos_renyi_graph

# Run the models
ltm_active_nodes = linear_threshold_model(G, ltm_thresholds, seed_size)
icm_active_nodes = independent_cascade_model(G, icm_probability, seed_size)

# Print the results
print(f"Active nodes in LTM: {len(ltm_active_nodes)}")
print(f"Active nodes in ICM: {len(icm_active_nodes)}")
plt.figure(figsize=(12, 8))
pos = nx.spring_layout(G)
nx.draw_networkx_edges(G, pos, alpha=0.1)
nx.draw_networkx_nodes(G, pos, nodelist=ltm_active_nodes,node_size=6, node_color='r', label='LTM Active Nodes')
nx.draw_networkx_nodes(G, pos, nodelist=icm_active_nodes,node_size=6, node_color='b', label='ICM Active Nodes')
plt.legend()
plt.title('Linear Threshold Model and Independent Cascade Model on Erdos Renyi Network')
plt.show()
Active nodes in LTM: 10
Active nodes in ICM: 4007

The difference in active nodes between the Linear Threshold Model (LTM) and the Independent Cascade Model (ICM) in the Erdos-Renyi graph is quite stark:

In the LTM, we again see that only 10 nodes are active, which suggests that the threshold for activation might be set high, or perhaps the initial set of active nodes had limited influence.

In contrast, the ICM has a far greater impact with 4,007 active nodes, which aligns with the random nature of Erdos-Renyi graphs where the uniform probability of edge creation can facilitate widespread activation due to the independent chances each node has to activate its neighbors.

5.3.0. Linear Threshold Model and Independent Cascade Model on Watts Strogatz Network

In [28]:
G=watts_strogatz_graph

# Run the models
ltm_active_nodes = linear_threshold_model(G, ltm_thresholds, seed_size)
icm_active_nodes = independent_cascade_model(G, icm_probability, seed_size)

# Print the results
print(f"Active nodes in LTM: {len(ltm_active_nodes)}")
print(f"Active nodes in ICM: {len(icm_active_nodes)}")
plt.figure(figsize=(12, 8))
pos = nx.spring_layout(G)
nx.draw_networkx_edges(G, pos, alpha=0.1)
nx.draw_networkx_nodes(G, pos, nodelist=ltm_active_nodes,node_size=6, node_color='r', label='LTM Active Nodes')
nx.draw_networkx_nodes(G, pos, nodelist=icm_active_nodes,node_size=6, node_color='b', label='ICM Active Nodes')
plt.legend()
plt.title('Linear Threshold Model and Independent Cascade Model on Watts Strogatz Network')
plt.show()
Active nodes in LTM: 10
Active nodes in ICM: 3988

LTM Active Nodes: Only 10 nodes have been activated. The LTM's low number suggests that very few nodes crossed the threshold needed for activation, which might indicate that the thresholds set for activation are relatively high or that the initial set of active nodes was quite limited.

ICM Active Nodes: There's a significantly higher count of 3,988 active nodes, showing that the cascade effect of activation in the ICM is much more widespread in this network. The nature of the ICM, with each active node having a chance to activate each of its neighbors independently, usually results in more widespread activation, especially in networks with a high degree of connectivity.

5.4.0. Linear Threshold Model and Independent Cascade Model on Barabasi Albert Network

In [29]:
G=barabasi_albert_graph

# Run the models
ltm_active_nodes = linear_threshold_model(G, ltm_thresholds, seed_size)
icm_active_nodes = independent_cascade_model(G, icm_probability, seed_size)

# Print the results
print(f"Active nodes in LTM: {len(ltm_active_nodes)}")
print(f"Active nodes in ICM: {len(icm_active_nodes)}")
plt.figure(figsize=(12, 8))
pos = nx.spring_layout(G)
nx.draw_networkx_edges(G, pos, alpha=0.1)
nx.draw_networkx_nodes(G, pos, nodelist=ltm_active_nodes,node_size=6, node_color='r', label='LTM Active Nodes')
nx.draw_networkx_nodes(G, pos, nodelist=icm_active_nodes,node_size=6, node_color='b', label='ICM Active Nodes')
plt.legend()
plt.title('Linear Threshold Model and Independent Cascade Model on Barabasi Albert Network')
plt.show()
Active nodes in LTM: 10
Active nodes in ICM: 3815

LTM Active Nodes: Only 10 nodes have been activated. The LTM's low number suggests that very few nodes crossed the threshold needed for activation, which might indicate that the thresholds set for activation are relatively high or that the initial set of active nodes was quite limited.

ICM Active Nodes: There's a significantly higher count of 3,815 active nodes, showing that the cascade effect of activation in the ICM is much more widespread in this network. The nature of the ICM, with each active node having a chance to activate each of its neighbors independently, usually results in more widespread activation, especially in networks with a high degree of connectivity.

6.0.0. Research Question¶

Analyzing Community Structures and Bridge Nodes in a Social Network¶

Social networks offers insights into human behavior, information dissemination, and the dynamics of societal relationships. This report examines the structural nuances of a social network, highlighting community structures, bridge nodes, and their implications on network robustness and information flow. Through comparative analysis with theoretical models such as Erdos–Renyi, Watts-Strogatz, and Barabasi-Albert graphs, we draws insights into the characteristics of real-world networks.

Network Overview¶

The Facebook network has 4,039 nodes connected by 88,234 edges . This demonstrates a richly interconnected structure with an average degree of 43.69. It also suggests a well-connected topology where nodes, on average, link to approximately 44 others. This network is characterized by a scale-free property, as indicated by its degree distribution, with a few highly connected hubs and many nodes with fewer links. The average clustering coefficient of 0.606 points towards a tightly-knit community structure, typical of social networks. Despite its sparse graph density of 0.0108, the network exhibits robustness against random failures, albeit with vulnerabilities to targeted attacks on key nodes.

Comparative Analysis with Theoretical Models¶

Erdős–Rényi Graph The Erdős–Rényi model, known for its random edge placement, shows a normally distributed degree distribution around an average degree of 43.579. Its low clustering coefficient (0.011) and short average shortest path length (2.607) highlight a random but efficient network structure, lacking the tight-knit community structures of real-world networks.

Watts-Strogatz Graph Reflecting small-world properties, the Watts-Strogatz model starts with a regular lattice and introduces randomness through rewiring. The graph has an average degree of 44 and a clustering coefficient of 0.377, it captures the essence of local clustering and short path lengths characteristic of social networks, though it still simplifies the complex structures observed in the Facebook network.

Barabási-Albert Graph The Barabási-Albert model, embodying scale-free properties, best mirrors the Facebook network's degree distribution, showcasing a few nodes with high connectivity and many with lower degrees. It consists of average degree (41.782), clustering coefficient (0.037), and shortest average path length (2.533), thus, underscores the network's efficiency and the significant role of hubs.

Community Structures and Bridge Nodes The analysis of eigenvector centrality, PageRank, degree centrality, closeness centrality, betweenness centrality, and Katz centrality within the Facebook network reveals key nodes that serve as major hubs or bridges within the community. For instance, node 107, with the highest degree centrality (0.259) and closeness centrality, acts as a pivotal connector, efficiently spreading information across the network. Similarly, node 1912 stands out with the highest eigenvector and Katz centrality scores, indicating its role in the network's core structure and influence.

Implications The presence of influential nodes and a high clustering coefficient in the Facebook network suggests a robust yet potentially vulnerable structure. While the network can withstand random node failures, targeted attacks on bridge nodes or hubs could disrupt information flow significantly. The comparative analysis with theoretical models emphasizes the unique properties of real-world networks, such as scale-free distribution and tight community structures, not fully captured by models like Erdős–Rényi or Watts-Strogatz.

Conclusion The study of the Facebook network through the lens of theoretical models reveals the intricate balance between robustness and vulnerability inherent in social networks. Understanding the role of community structures and bridge nodes in such networks is crucial for designing resilient systems and effective strategies for information dissemination and control. This analysis underscores the importance of network topology in the dynamics of social interactions and the potential impact of strategic interventions.